{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.7.5"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3
 },
 "cells": [
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 11. 盛最多水的容器"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。\n",
    "\n",
    "说明：你不能倾斜容器，且 n 的值至少为 2。\n",
    "\n",
    "\n",
    "\n",
    "图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。\n",
    "\n",
    "![](https://aliyun-lc-upload.oss-cn-hangzhou.aliyuncs.com/aliyun-lc-upload/uploads/2018/07/25/question_11.jpg)\n",
    "\n",
    "示例:\n",
    "\n",
    "输入: [1,8,6,2,5,4,8,3,7]\n",
    "输出: 49\n",
    "\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/container-with-most-water"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## 方法1：暴力法\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "49\n"
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def maxArea(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        maxArea = 0\n",
    "        for i in range(len(height)):\n",
    "            for j in range(i,len(height)):\n",
    "                maxArea = max(maxArea,min(height[j], height[i]) * (j-i))\n",
    "\n",
    "        return maxArea\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    Sol = Solution()\n",
    "    end = Sol.maxArea([1,8,6,2,5,4,8,3,7])\n",
    "    print(end)"
   ]
  },
  {
   "cell_type": "markdown",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "## 方法2：双指针"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "49\n"
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def maxArea(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        maxArea = 0\n",
    "        l,r = 0,len(height)-1\n",
    "        while l < r:\n",
    "            maxArea = max(maxArea, min(height[l], height[r]) * (r - l))\n",
    "            if height[l] < height[r]:\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "        return maxArea\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    Sol = Solution()\n",
    "    end = Sol.maxArea([1,8,6,2,5,4,8,3,7])\n",
    "    print(end)"
   ]
  }
 ]
}